package cn.aylog.example;

import java.util.Arrays;

/**
 * 动态规划
 */
public class DynamicProgramming {
    public static void main(String[] args) {
        maxValue();
    }

    /**
     * 01背包，自底向上
     */
    public static void maxValue() {
        int maxWeight = 4; // 最大背包容量
        int many = 3; // 有三件物品可选
        int[][] value = new int[many+1][maxWeight+1];
        int[] v = {0, 1500, 3000, 2000};
        int[] w = {0, 1, 4, 3};
        String[][] caps = new String[many+1][maxWeight+1]; // 记录背包物品
        for(int x=1; x<=many; x++) {
            for(int y=1; y<=maxWeight; y++) {
                // value[x][y] = v[x];
                if(w[x] > y) {
                    // 物品占用 》 背包容量 => 背包装不进
                    value[x][y] = value[x-1][y];
                    caps[x][y] = "<" + (x-1) + ">";

                } else {
                    // 获取最大价值
                    if(value[x-1][y] < v[x] + value[x-1][y - w[x]]) {
                        value[x][y] = v[x] + value[x-1][y - w[x]];
                        if(value[x-1][y-w[x]] > 0) {
                            caps[x][y] = "<" + x + " " + caps[x-1][y - w[x]] + ">";
                        } else {
                            caps[x][y] = "<" + x + ">";
                        }
                    } else {
                        value[x][y] = value[x-1][y];
                        caps[x][y] = "<" + (x-1) + ">";
                    }
                }
            }
        }
        // for(int[] row : value) {
        //     System.out.println(Arrays.toString(row));
        // }
        for(String[] cap : caps) {
            System.out.println(Arrays.toString(cap));
        }

    }
}
